package problem145_Binary_Tree_Postorder_Traversal;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import problem105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.MySolution.TreeNode;

public class SolutionNonRecursive {
	public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> result=new LinkedList<>();
		Stack<TreeNode> stack=new Stack<>();
		if(root!=null)	stack.push(root);
		TreeNode pre=null;
		while(!stack.isEmpty()){
			TreeNode curr=stack.peek();
			if((curr.left==null&&curr.right==null)||
					(pre!=null&&(curr.left==pre||curr.right==pre))){
				pre=curr;
				result.add(stack.pop().val);
			}else{
				if(curr.right!=null)
					stack.push(curr.right);
				if(curr.left!=null)
					stack.push(curr.left);
			}
		}
		return result;		
	}
}
